import java.util.*;

import java.util.Stack;

//现有一链表的头指针 ListNode* pHead，给一定值x，编写一段代码将所有小于x的结点排在其余结点之前，
// 且不能改变原来的数据顺序，返回重新排列后的链表的头指针。
public class Partition {
    public ListNode partition(ListNode pHead, int x) {
        if(pHead==null){
            return null;
        }
        ListNode cur=pHead;
        ListNode prev=null;
        Stack<Integer> stack=new Stack<Integer>();

        while(cur!=null){
            if(cur.val<x){
                stack.add(cur.val);
                //添加到栈中的结点又分是否是头结点
                if(cur==pHead){
                    //删除并更新头结点 更新当前结点
                    pHead=pHead.next;
                    cur=pHead;
                }else{
                    //删除并更新当前结点
                    cur=cur.next;
                    prev.next=cur;
                }
            }else{
                prev=cur;
                cur=cur.next;

            }

        }

        while(!stack.isEmpty()){
            ListNode newNode=new ListNode(stack.pop());
            newNode.next=pHead;
            pHead=newNode;

        }
        return pHead;

    }
}